Syllabus for CSC 4170-50
Theory of Computation
Spring
1996
Tuesday-Thursday, 6:00 p.m. -- 7:15 p.m.
Mendel
258
Instructor: David Matuszek, david.l.matuszek@lmco.com
These pages are best viewed using Netscape Navigator 2.0. Mosaic has a
bug that prevents links within the table from working; earlier versions of
Netscape do not support subscripts and superscripts. You can download Netscape
Navigator 2.0 by clicking the following button:
Email is by far the best way to contact me. During the workday I can usually
respond almost immediately--if I don't, I'm probably tied up in a meeting. I
don't usually check email in the evenings, and only occasionally on weekends.
Textbook: An Introduction to Formal Languages and Automata
Peter Linz,
ISBN 0-669-17342-8
Here are some comparable courses I've found on the
Web:
Links to other
relevant pages will be found in the appropriate lessons.
Grades will be based primarily on exams. I expect to grade 20% homework, 30%
midterm, and 50% final exam. (The final exam will be comprehensive.) These
numbers may be modified slightly depending on the amount of homework I assign.
Here are the topics we will cover and the relevant chapters in the book.
Dates are tentative.
| Date |
Chapter |
Topic |
| Jan 16 |
1.1 |
Introduction
and review |
| Jan 18 |
---- |
BNF |
| Jan 23 |
1.2 |
Languages,
grammars, and automata (most important!) |
| Jan 25 |
2.1 |
DFAs
and their implementation |
| Jan 30 |
2.2 |
NDFAs
and their implementation |
| Feb 1 |
2.3 |
DFAs =
NDFAs |
| Feb 6 |
3.1 |
Regular
expressions |
| Feb 8 |
3.2 |
Regular
expressions denote regular languages |
| Feb 13 |
3.3 |
Regular
grammars |
| Feb 15 |
4.1, 4.2 |
Closure,
homomorphism |
| Feb 20 |
4.3 |
Pigeonhole
principle, pumping lemma (difficult) |
| Feb 22 |
---- |
Review for midterm |
| Feb 27 |
---- |
Midterm exam |
| Feb 29 |
5.1 |
CFGs |
| Mar 5 |
5.2 |
Parsing
and ambiguity |
| Mar 7 |
7.1 |
Pushdown
automata |
| Mar 19 |
7.2, 7.3 |
NPDAs
& CFGs |
| Mar 21 |
8.1 |
A
pumping lemma for cfgs (still difficult) |
| Mar 26 |
9.1 |
Turing
machines |
| Mar 28 |
10.4, 10.5 |
Universal
Turing Machines and LBAs |
| Apr 2 |
11.1 |
Recursively
enumerable languages |
| Apr 9 |
11.2 |
Unrestricted
grammars |
| Apr 11 |
11.3, 11.4 |
The
Chomsky hierarchy |
| Apr 16 |
12.1 |
Undecidable
problems |
| Apr 18 |
13.1 |
Church's
Thesis |
| Apr 23 |
13.2 |
Complexity
Theory, P and NP |
| Apr 25 |
all |
Review for
Final |
| Apr 30 |
---- |
Go over homework, Q & A |
| May 7 |
Cumulative |
Final exam 5:30-7:30 |
Copyright © 1996 by David Matuszek
Last
modified Apr 23, 1996 |
|